<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script src="queue.js"></script>
<script src="dict.js"></script>
<script>
    // 封装图结构
    function Graph () {
        // 属性 ： 顶点（数组）\ 边（字典）
        this.vertexes = []
        this.edges = new Dictionay()

        // 方法
        // 添加方法
        // 1.添加顶点的方法
        Graph.prototype.addVertex = function (v) {
            this.vertexes.push(v)
            this.edges.set(v, [])
        }

        // 2.添加边
        Graph.prototype.addEdges = function (v1, v2) {
            this.edges.get(v1).push(v2)
            this.edges.get(v2).push(v1)
        }

        // 实现toString方法
        Graph.prototype.toString = function () {
            // 定义字符串，保存最终的结果
            var resultString = ''

            // 遍历所有的顶点，以及所有的边
            for (var i = 0; i < this.vertexes.length; i++) {
                resultString += this.vertexes[i] + '=>'
                var vEdges = this.edges.get(this.vertexes[i])
                for (var j = 0; j < vEdges.length; j++) {
                    resultString += vEdges[j] + ' '

                }
                resultString += '\n'
            }

            return resultString
        }


        // 初始化颜色状态
        Graph.prototype.initializeColor = function () {
            var colors = []
            for (var i = 0; i < this.vertexes.length; i++) {
                colors[this.vertexes[i]] = 'white'
            }
            return colors
        }

        // 实现广度优先搜索（BFS）
        Graph.prototype.bfs = function (initV, handler){
            // 1.初始化颜色
            var colors = this.initializeColor()

            // 2.创建队列
            var queue = new Queue()

            // 3.将顶点加入队列
            queue.enqueue(initV)

            // 4.循环从队列取出元素
            while (!queue.isEmpty()) {
                // 4.1.从队列中取出一个顶点
                var v = queue.dequeue()

                // 4.2获取于顶点相邻的节点
                var vList = this.edges.get(v)

                // 4.3将顶点的颜色变为灰色
                colors[v] = 'gray'

                // 4.4遍历所有的顶点并加入队列中
                for (var i = 0; i < vList.length; i++) {
                    var e = vList[i]
                    if (colors[e] == 'white') {
                        colors[e] = 'gray'
                        queue.enqueue(e)
                    }
                }
                // 4.5 访问顶点
                handler(v)

                // 4.6将顶点赋值为黑色
                colors[v] = 'black'
            }
        }


        // 深度优先搜索（DFS）
        Graph.prototype.dfs = function (initV, handler) {
            // 1.初始化颜色
            var colors = this.initializeColor()
            // 2.从某个顶点一次递归访问
            this.dfsVisit(initV, colors, handler)

        }
        Graph.prototype.dfsVisit = function (v, colors, handler) {
            // 1.将颜色设置为灰色
            colors[v] = 'gray'

            // 2.处理顶点v
            handler(v)

            // 3.访问与v相连的顶点
            var vList = this.edges.get(v)
            for (var i = 0; i < vList.length; i++) {
                var e = vList[i]
                if (colors[e] == 'white') {
                    this.dfsVisit(e, colors, handler)
                }
            }
            // 4.将v设置成黑色
            colors[v] = 'black'
        }
    }

    // 测试代码
    // 1.创建图结构
    var graph = new Graph()

    // 2.添加顶点
    var myVertexes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
    for (var i = 0; i < myVertexes.length; i++) {
        graph.addVertex(myVertexes[i])
    }

    // 3.添加边
    graph.addEdges('A', 'B')
    graph.addEdges('A', 'C')
    graph.addEdges('A', 'D')
    graph.addEdges('C', 'D')
    graph.addEdges('C', 'G')
    graph.addEdges('D', 'G')
    graph.addEdges('D', 'H')
    graph.addEdges('B', 'E')
    graph.addEdges('B', 'F')
    graph.addEdges('E', 'I')

    // 4.测试结果
    alert(graph)

    // 5.测试bfs
    // var result = ''
    // graph.bfs(graph.vertexes[0], function (v) {
    //     result += v + ' '
    // })
    // alert(result)

    // 测试dfs
    var result = ''
    graph.dfs(graph.vertexes[0], function (v) {
        result += v + ' '
    })
    alert(result)

</script>
</body>
</html>
